package com.datastructure.test.pickwater;

public class PickWater {
   private int sum = 0;
    public static void main(String[] args) {
        int[] data = {1,1,1,1};
        PickWater pickWater = new PickWater();
        System.out.println(pickWater.maxWater(data));
    }

    public long maxWater (int[] arr) {
        // write code here
        int max = 0;
        int indexI = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>=max){
                max=arr[i];
                indexI = i;
            }
        }
        if(max==0||max==1){
            return 0;
        }
        dfsLeft(arr,0,indexI);
        dfsRight(arr,indexI,arr.length);
        return sum;
    }

    public void dfsRight(int[] arr,int left,int right){
        if(left==right){
            return;
        }
        int max = 0;
        int indexI = Integer.MAX_VALUE;
        for (int i = left+1; i < right; i++) {
            if(arr[i]>=max){
                max=arr[i];
                indexI = i;
            }
        }
        if(indexI!=Integer.MAX_VALUE) {
            dfsRight(arr, indexI, right);
            sum += ((indexI - left - 1) * max);
            for (int i = left + 1; i < indexI; i++) {
                sum -= arr[i];
            }
        }
    }

    public void dfsLeft(int[] arr,int left,int right){
        if(left==right){
            return;
        }
        int max = 0;
        int indexI = Integer.MAX_VALUE;
        for (int i = left; i < right; i++) {
            if(arr[i]>=max){
                max=arr[i];
                indexI = i;
            }
        }
        if(indexI!=Integer.MAX_VALUE) {
            dfsLeft(arr, left, indexI);
            sum += ((right - indexI - 1) * max);
            for (int i = indexI + 1; i < right; i++) {
                sum -= arr[i];
            }
        }
    }
}
